This invention relates to image analyzer systems and, more particularly, to pattern recognition and analysis devices utilizing a series of neighborhood transformations.
A wide variety of applications exist in which it would be desirable for a machine to automatically recognize, analyze, and/or classify patterns existing in images which have been sensed and converted to some sort of matrix of electrical signals. Some of the simpler problems, which have been implemented with at least limited success by machines, include the recognition of alphanumeric characters and recognitional counting of certain particles, such as blood cells. (See, e.g. U.S. Pat. Nos. 3,846,754 to Oka; 3,196,398 to Baskin; 3,573,789 to Sharp; 3,761,876 to Flaherty; 3,287,703 to Slotnick; 3,899,771 to Saraga et al.; 3,959,771 to Uno et al.; and 4,110,736 to Kono.)
Elaborate programs have been written for general purpose computers to perform pattern analysis and classification. The limited success of the general purpose computer in performing pattern analysis and classification is due to the extremely long processing time to process images with very many data points or pixels. A more promising approach is the use of special purpose processors which implement a mathmatical technique applicable to data in the form of images, integral geometry being such a technique. One such approach considers the input data as an M by N array of zeroes and ones representing black or white picture elements. From the input array another M by N array is derived wherein each point in the second array is a function of the state of the equivalent point in the initial array. A series of these transforms may be performed to determine some of the characteristics of patterns displayed in the initial array. For example, U.S. Pat. No. 3,241,547 discloses a special purpose image processor used for counting lympocytes in blood. Devices employing similar forms of processors for implementing these so called "neighborhood transforms" are disclosed in Pattern Detection and Recognition by Unger, Proceedings of the I.R.E. 1959, page 737; Feature Extraction by Goley; Hexogonal Pattern Transforms, Preston, Jr., IEEE Transactions on Computers, Vol. C-20, No. 9, Sept. 1971; and A Parallel Picture Processing Machine by Kruse, IEEE Transactions on Computers, Vol. C-22, No. 12, Dec. 1973.
Another class of special purpose machines for implementing a form of integral geometry analysis employing what the author terms "hit-or-miss transformations" is disclosed in "The Texture Analyzer", Journal of Microscopy, Volume 95, Part II, April 1972, pages 349-356.
Many of these prior art image processors require that the data points in the image to be reduced to binary form, either zero or one, in accordance with the conventional requirements of integral geometry. For applications of integral geometry in pattern recognition see:
1. G. Matheron, Random Sets and Integral Geometry, Wiley, 1975. PA1 2. Albert B. J. Novikoff, "Integral Geometry As A Tool In Pattern Reception", in Principals of Self Organization, edited by Von Foerstn and Zopf, Pergamon Press, 1962. PA1 3. J. Sera, "Stereology and Structuring Elements", Journal of Microscopy, Vol. 95, Part 1, February 1972, pages 93-103.
A new class of image analyzer processors is disclosed in U.S. Pat. No. 4,167,728 to Sternberg, which is assigned to the assignee of the present invention. That patent discloses a serial chain of substantially identical neighborhood transformation modules. The image data, generally in the form of raster scan lines, is serially shifted through a neighborhood portion in each stage for sequentially accessing substantially all of the neighborhoods in the image matrix. Depending upon the states of the pixels contained in the neighborhood extraction portion, certain transformations are performed and the transformed output is passed on to the input of the succeeding stage. A central controller, which is coupled to all of the stages, defines all of the particular transformation analyses to be performed in the stages.
U.S. Pat. No. 4,174,514 to Sternberg, also assigned to the assignee of the present invention, discloses a technique by which the image data is partitioned and fed through associated parallel processors making up each stage.
U.S. patent application Ser. No. 73,818 to Sternberg, filed Sept. 10, 1979, now U.S. Pat. No. 4,322,716, and assigned to the assignee of the present invention, discloses pattern recognition circuitry capable of analyzing three dimensional images represented by multi-valued pixel image data. The specific embodiment shown in that application utilizes two different pipelines of transformation stages, one for two-dimensional image analysis andone for three-dimensional image analysis. While the stages in each pipeline are substantially identical, the stages in one pipeline differ from those in the other pipeline. The stages in the two dimensional pipeline are specifically adapted to perform transformations generally associated with two-dimensional image data, while the stages in the three dimensional pipeline are particularly adapted for performing three dimensional data analysis. A central controller routes the image data to one or the other of the pipelines depending upon the type of analysis to be performed, with the central controller being parallel coupled to the control portions of each stage. The controller sends control instructions to the transformation logic to define the type of transformation to be generated in each stage of the selected pipeline.
The aforementioned commonly assigned patents are hereby incorporated by reference.